{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pizza With 3n Slices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSizeSlices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #3n 块披萨"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你挑选 <strong>任意</strong>&nbsp;一块披萨。</li>\n",
    "\t<li>Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。</li>\n",
    "\t<li>Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。</li>\n",
    "\t<li>重复上述过程直到没有披萨剩下。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每一块披萨的大小按顺时针方向由循环数组 <code>slices</code>&nbsp;表示。</p>\n",
    "\n",
    "<p>请你返回你可以获得的披萨大小总和的最大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/sample_3_1723.png\" style=\"height: 240px; width: 475px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>slices = [1,2,3,4,5,6]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/sample_4_1723.png\" style=\"height: 250px; width: 475px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>slices = [8,9,8,6,1,1]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= slices.length &lt;= 500</code></li>\n",
    "\t<li><code>slices.length % 3 == 0</code></li>\n",
    "\t<li><code>1 &lt;= slices[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pizza-with-3n-slices](https://leetcode.cn/problems/pizza-with-3n-slices/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pizza-with-3n-slices](https://leetcode.cn/problems/pizza-with-3n-slices/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6]', '[8,9,8,6,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        \n",
    "        new = [[slices[i],i-1,i+1] for i in range(n) ]\n",
    "        new[0][1] = n-1\n",
    "        new[n-1][2] = 0\n",
    "        #print(new)\n",
    "        \n",
    "        mark = list(zip([-i for i in slices],range(n)))\n",
    "        print(mark)\n",
    "        heapify(mark)\n",
    "        print(mark)\n",
    "        target = n//3\n",
    "        ans = 0\n",
    "        #print(mark)\n",
    "\n",
    "        while target > 0:\n",
    "            x,y = heappop(mark)\n",
    "            l = new[y][1]\n",
    "            while new[l][2] != y:\n",
    "                x,y = heappop(mark)\n",
    "                l = new[y][1]\n",
    "            \n",
    "            r = new[y][2]\n",
    "            new[y][0] = new[l][0] + new[r][0] - new[y][0]\n",
    "            nl = new[l][1]\n",
    "            nr = new[r][2]\n",
    "            new[y][1] = nl\n",
    "            new[y][2] = nr\n",
    "            new[nl][2] = y\n",
    "            new[nr][1] = y\n",
    "            ans -= x\n",
    "            heappush(mark,(-new[y][0],y))\n",
    "            target -= 1\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        def helper(nums):\n",
    "            n = len(nums)\n",
    "            m = (n + 1) // 3\n",
    "            f = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "            f[0][1] = nums[0]\n",
    "            f[1][1] = max(nums[0], nums[1])\n",
    "            for i in range(2, n):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][j] = max(f[i - 2][j - 1] + nums[i], f[i - 1][j])\n",
    "            return f[n - 1][m]\n",
    "        return max(helper(slices[1: ]), helper(slices[: -1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 解题思路：强化版的打家劫舍\n",
    "# 证明：题目可转化为在3n长度的数组中选取不相邻的n个数，求最大和\n",
    "# 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+slices[i])，如果选前一个数，就不能选当前数，如果选前2个数，那么可以选当前数\n",
    "# 循环数组如何处理，分别去除数组中的第一个数和最后一个数，分别dp，表示这两个数不能同时选，两个dp的最大值即为答案\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        m = len(slices)\n",
    "        n = m // 3\n",
    "        dp1 = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp2 = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp1[2][1] = slices[1]\n",
    "        dp1[3][1] = max(slices[1], slices[2])\n",
    "        for i in range(3, m):\n",
    "            for j in range(1, n+1):\n",
    "                dp1[i+1][j] = max(dp1[i][j], dp1[i-1][j-1]+slices[i])\n",
    "        dp2[1][1] = slices[0]\n",
    "        dp2[2][1] = max(slices[0], slices[1])\n",
    "        for i in range(2, m-1):\n",
    "            for j in range(1, n+1):\n",
    "                dp2[i+1][j] = max(dp2[i][j], dp2[i-1][j-1]+slices[i])\n",
    "        return max(dp1[m][n], dp2[m-1][n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        # 好像只要不是相连接的两个数字就可以选取\n",
    "        n = len(slices)\n",
    "        nn = n // 3\n",
    "\n",
    "        # 选第一个 # 最后一个不能选\n",
    "        lis = [[0] * (n-1) for _ in range(nn)]\n",
    "        lis[0][:] = slices[:(n-1)]\n",
    "\n",
    "        for i in range(1, nn):\n",
    "            dp0 = max(lis[i-1][:i*2-1])\n",
    "            for j in range(i*2, n-1):\n",
    "                lis[i][j] = slices[j] + dp0\n",
    "                dp0 = max(dp0, lis[i-1][j-1])\n",
    "        \n",
    "        # 选第二个 # 最后一个可以选\n",
    "        lis2 = [[0] * (n-1) for _ in range(nn)]\n",
    "        lis2[0][:] = slices[1:]\n",
    "\n",
    "        for i in range(1, nn):\n",
    "            dp0 = max(lis2[i-1][:i*2-1])\n",
    "            for j in range(i*2, n-1):\n",
    "                lis2[i][j] = slices[j+1] + dp0\n",
    "                dp0 = max(dp0, lis2[i-1][j-1])\n",
    "        \n",
    "        return max(max(lis[-1]), max(lis2[-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        f1 = [[0] * (n + 1) for _ in range(n // 3 + 1)] # f[分到的块数][前一块的idx] = 这么操作的最大值\n",
    "        f2 = [[0] * (n + 1) for _ in range(n // 3 + 1)]\n",
    "        f1[1][1] = slices[0] # 选第1块的边界条件\n",
    "        f2[0][0] = 0 # 不选第1块的边界条件\n",
    "        for i in range(1, n // 3):\n",
    "            mx= 0\n",
    "            for j in range(3, n):\n",
    "                mx = max(mx, f1[i][j - 2])\n",
    "                f1[i + 1][j] = mx + slices[j - 1]\n",
    "        for i in range(n // 3):\n",
    "            mx = 0\n",
    "            for j in range(2, n + 1):\n",
    "                mx = max(mx, f2[i][j - 2])\n",
    "                f2[i + 1][j] += mx + slices[j - 1]\n",
    "        return max(max(f1[n // 3]), max(f2[n // 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    slices = []\n",
    "    d = {}\n",
    "    def getMaxSizeSlices(self, begin: int, end: int, n: int) -> int:\n",
    "        if 2 * n - 1 > end - begin:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return max(self.slices[begin:end])\n",
    "        else:\n",
    "            if end - begin == len(self.slices):\n",
    "                if f\"{begin+2}_{end-1}_{n-1}\" not in self.d:\n",
    "                    self.d[f\"{begin+2}_{end-1}_{n-1}\"] = self.getMaxSizeSlices(begin=begin + 2, end=end - 1, n=n - 1)\n",
    "                if f\"{begin+1}_{end}_{n}\" not in self.d:\n",
    "                    self.d[f\"{begin+1}_{end}_{n}\"] = self.getMaxSizeSlices(begin=begin + 1, end=end, n=n)\n",
    "                a1 = self.slices[begin] + self.d[f\"{begin+2}_{end-1}_{n-1}\"]\n",
    "                a2 = self.d[f\"{begin+1}_{end}_{n}\"]\n",
    "                return max(a1, a2)\n",
    "            else:\n",
    "                if f\"{begin+2}_{end}_{n-1}\" not in self.d:\n",
    "                    self.d[f\"{begin+2}_{end}_{n-1}\"] = self.getMaxSizeSlices(begin=begin + 2, end=end, n=n - 1)\n",
    "                if f\"{begin+1}_{end}_{n}\" not in self.d:\n",
    "                    self.d[f\"{begin+1}_{end}_{n}\"] = self.getMaxSizeSlices(begin=begin + 1, end=end, n=n)\n",
    "                a1 = self.slices[begin] + self.d[f\"{begin+2}_{end}_{n-1}\"]\n",
    "                a2 = self.d[f\"{begin+1}_{end}_{n}\"]\n",
    "                return max(a1, a2)\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        self.slices = slices\n",
    "        self.d = {}\n",
    "        return self.getMaxSizeSlices(begin=0, end=len(slices), n=len(slices)//3)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        #打家劫舍→环状序列，打劫了一家之后旁边两家不能打劫，此种情况下的最大值。\n",
    "        #不同的是，这里每次打劫之后，都会新增2处不可打劫的地方而非不变化→使用仅能打劫n//3处地方来进行限制\n",
    "        #3n个数中选择n个不相邻的数，使得和最大\n",
    "        def g(slices):\n",
    "            # 函数g是用于掐头和去尾的\n",
    "            # 在nums中选择n个数的，和最大\n",
    "            # dp[i][j]记录的是 在前i个数中，选择j个不相邻的数，和最大\n",
    "            n = len(slices)//3\n",
    "            dp = [[-1]*(n+1) for i in range(len(slices)+1)]\n",
    "            \n",
    "            # dp 需要进行初始化\n",
    "            # 在前0个数中，选择j个不相邻的数肯定为0\n",
    "            dp[0] = [0] * (n+1)\n",
    "            # 在前1个数中，选择j个不相邻的数肯定为该数，除了j = 0时\n",
    "            dp[1] = [slices[0]] * (n+1)\n",
    "            # 在前i个数中，选择0个不相邻的数肯定为0\n",
    "            for i in range(len(slices)+1):\n",
    "                dp[i][0] = 0\n",
    "            \n",
    "            def func(i,j,nums):\n",
    "                # if i<0 or j<0:\n",
    "                #     return 0\n",
    "                if dp[i][j] != -1:\n",
    "                    # 有值\n",
    "                    return dp[i][j]\n",
    "                else:\n",
    "                    tmp = max(func(i-1,j,nums), func(i-2,j-1,nums)+nums[i-1])\n",
    "                    dp[i][j] = tmp\n",
    "                    return tmp\n",
    "            # 3n个数中选择n个数\n",
    "            return func(3*n, n ,slices)\n",
    "        # 掐头和去尾：\n",
    "        return max(g(slices[1:]+[0]), g(slices[:-1]+[0]))\n",
    "           \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        #打家劫舍→环状序列，打劫了一家之后旁边两家不能打劫，此种情况下的最大值。\n",
    "        #不同的是，这里每次打劫之后，都会新增2处不可打劫的地方而非不变化→使用仅能打劫n//3处地方来进行限制\n",
    "        #3n个数中选择n个不相邻的数，使得和最大\n",
    "        def g(slices):\n",
    "            # 函数g是用于掐头和去尾的\n",
    "            # 在nums中选择n个数的，和最大\n",
    "            # dp[i][j]记录的是 在前i个数中，选择j个不相邻的数，和最大\n",
    "            n = len(slices)//3\n",
    "            dp = [[-1]*(n+1) for i in range(len(slices)+1)]\n",
    "            \n",
    "            # dp 需要进行初始化\n",
    "            # 在前0个数中，选择j个不相邻的数肯定为0\n",
    "            dp[0] = [0] * (n+1)\n",
    "            # 在前1个数中，选择j个不相邻的数肯定为该数，除了j = 0时\n",
    "            dp[1] = [slices[0]] * (n+1)\n",
    "            # 在前i个数中，选择0个不相邻的数肯定为0\n",
    "            for i in range(len(slices)+1):\n",
    "                dp[i][0] = 0\n",
    "            # 滚动更新法\n",
    "            # dp[i][j] = max(func(i-1,j,nums), func(i-2,j-1,nums)+nums[i-1])\n",
    "            # dp[i][j] 仅和 dp[i-1][j] 和 dp[i-2][j-1]有关\n",
    "            # 即可以更与前两行更新该行\n",
    "            for i in range(2,len(slices)+1):\n",
    "                for j in range(1,n+1):\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+slices[i-1])\n",
    "            print(dp)\n",
    "            def func(i,j,nums):\n",
    "                # if i<0 or j<0:\n",
    "                #     return 0\n",
    "                if dp[i][j] != -1:\n",
    "                    # 有值\n",
    "                    return dp[i][j]\n",
    "                else:\n",
    "                    tmp = max(func(i-1,j,nums), func(i-2,j-1,nums)+nums[i-1])\n",
    "                    dp[i][j] = tmp\n",
    "                    return tmp\n",
    "            # 3n个数中选择n个数\n",
    "            return dp[3*n][n]\n",
    "        # 掐头和去尾：\n",
    "        return max(g(slices[1:]+[0]), g(slices[:-1]+[0]))\n",
    "           \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        def maxArray(nums):#On garantit que nums.length>=5\n",
    "            dp=dict()\n",
    "            dp[0,1]=nums[0]\n",
    "            dp[1,1]=max(nums[0],nums[1])\n",
    "            for N in range(len(nums)):\n",
    "                dp[N,0]=0\n",
    "                if N>=2:dp[N,1]=max(dp[N-1,1], dp[N-2,0]+nums[N])\n",
    "                for k in range(2,len(slices)//3+1):\n",
    "                    if k>N: dp[N,k]=0\n",
    "                    else: dp[N,k]=max(dp[N-1,k], dp[N-2,k-1]+nums[N])\n",
    "            print(dp)\n",
    "            return dp[len(nums)-1, n//3]\n",
    "        n=len(slices)\n",
    "        if n==3: return max(slices)\n",
    "        else: return max(maxArray(slices[:n-1]), maxArray(slices[1:]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        slices1 = slices[0:n-1]\n",
    "        slices2 = slices[1:n]\n",
    "        dp1 = [[0] * (n+1) for _ in range(n-1)]\n",
    "        # print(dp)\n",
    "        dp2 = [[0] * (n+1) for _ in range(n-1)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(n+1):\n",
    "                if j == 0:\n",
    "                    dp1[i][j] = 0\n",
    "                elif i == 0 and j == 1:\n",
    "                    dp1[i][j] = slices1[0]\n",
    "                elif i == 1 and j == 1:\n",
    "                    dp1[i][j] = max(slices1[0], slices1[1])\n",
    "                elif i < 2 and j >= 2:\n",
    "                    dp1[i][j] == -100000000000000\n",
    "                else:\n",
    "                    dp1[i][j] = max(dp1[i-2][j-1] + slices1[i], dp1[i-1][j])\n",
    "        for i in range(n-1):\n",
    "            for j in range(n+1):\n",
    "                if j == 0:\n",
    "                    dp2[i][j] = 0\n",
    "                elif i == 0 and j == 1:\n",
    "                    dp2[i][j] = slices2[0]\n",
    "                elif i == 1 and j == 1:\n",
    "                    dp2[i][j] = max(slices2[0], slices2[1])\n",
    "                elif i < 2 and j >= 2:\n",
    "                    dp2[i][j] == -100000000000000\n",
    "                else:\n",
    "                    dp2[i][j] = max(dp2[i-2][j-1] + slices2[i], dp2[i-1][j])\n",
    "        temp = int(n/3)\n",
    "        return max(dp1[n-2][temp], dp2[n-2][temp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)        \n",
    "        K = n // 3\n",
    "                \n",
    "        # 到第i个位，共选了k个的最大得分\n",
    "        # dp[i][k][flag]\n",
    "        # flag，当前位置0不选 1选\n",
    "        dp = [[[0] * 2 for _ in range(K+1)] for _ in range(n)]\n",
    "        \n",
    "        # 因为是环，所以分两种情况\n",
    "        # 第一种，第0个位置的值不选        \n",
    "        # 初始化从1开始\n",
    "        dp[1][1][1] = slices[1]\n",
    "        \n",
    "        # 遍历剩下的值\n",
    "        for i in range(2,n):                        \n",
    "            # 最少一个，即自己，最多(i+1)//2+1，如i = 7 有 4个(1 3 5 7)\n",
    "            for k in range(1,min(K,(i+1)//2)+1):                \n",
    "                # 选当前值，不能连续选\n",
    "                # i-2选与i-1不选 \n",
    "                dp[i][k][1] = max(dp[i-2][k-1][1],dp[i-1][k-1][0]) + slices[i]\n",
    "                \n",
    "                # 不选当前值\n",
    "                dp[i][k][0] = max(dp[i-1][k][1],dp[i-1][k][0])\n",
    "        \n",
    "        res = max(dp[-1][K])\n",
    "        \n",
    "        # 第二种，第0个位置的值必选\n",
    "        # 则有两个限制，第一个位置不能选，最后一个位置也不能选        \n",
    "        # 初始化\n",
    "        dp = [[[0] * 2 for _ in range(K+1)] for _ in range(n)]\n",
    "        dp[0][1][1] = slices[0]\n",
    "        dp[1][1][0] = slices[0]\n",
    "        # 遍历剩下的值\n",
    "        # 第1个值和最后一个值都不能选\n",
    "        '''\n",
    "          2 2\n",
    "          3 2\n",
    "          4 3\n",
    "          5 3\n",
    "        '''\n",
    "        for i in range(2,n-1):     \n",
    "            for k in range(1,min(K,(i//2)+1)+1):\n",
    "                # 选当前值，不能连续选\n",
    "                # i-2选与i-1不选 \n",
    "                dp[i][k][1] = max(dp[i-2][k-1][1],dp[i-1][k-1][0]) + slices[i]\n",
    "                \n",
    "                # 不选当前值\n",
    "                dp[i][k][0] = max(dp[i-1][k][1],dp[i-1][k][0])\n",
    "                                \n",
    "        dp[n-1][K][0] = max(dp[n-2][K])\n",
    "                \n",
    "        res = max(res,max(dp[n-1][K]))\n",
    "        \n",
    "        return res                                                                       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "game theory.\n",
    "Brute force. select 1, remove 3. O(n^n).\n",
    "Select n non-adj items in a 3n cycle. get the max\n",
    "\n",
    "No cycle:\n",
    "dp[i][j] means select j items in the first i items.\n",
    "dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])\n",
    "\n",
    "Cycle:\n",
    "no first and last together.\n",
    "'''\n",
    "# DP O(n^2)\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        # select_first = self.get_max_size(slices[:-1])\n",
    "        # select_last = self.get_max_size(slices[1:])\n",
    "        self.slices = slices[:-1]\n",
    "        select_first = self.get_max_size(len(slices) - 2, len(slices)//3)\n",
    "        self.get_max_size.cache_clear()\n",
    "        self.slices = slices[1:]\n",
    "        select_last = self.get_max_size(len(slices) - 2, len(slices)//3)\n",
    "        return max(select_first, select_last)\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def get_max_size(self, idx, count):\n",
    "        m, n = len(self.slices), (len(self.slices) + 1) // 3\n",
    "        if count == 0:\n",
    "            return 0\n",
    "        if idx == 0:\n",
    "            return self.slices[0]\n",
    "        if idx == 1:\n",
    "            return max(self.slices[0], self.slices[1])\n",
    "        \n",
    "        return max(self.get_max_size(idx-1, count), self.get_max_size(idx-2, count-1) + self.slices[idx])\n",
    "\n",
    "    \n",
    "    # def get_max_size(self, slices):\n",
    "    #     N, n = len(slices), (len(slices) + 1) // 3 # slices here is subtructed one\n",
    "    #     dp = [[0] * (n+1) for _ in range(N)]\n",
    "    #     dp[0][0], dp[0][1] = 0, slices[0]\n",
    "    #     dp[1][0], dp[1][1] = 0, max(slices[0], slices[1])\n",
    "    #     for i in range(2, N):\n",
    "    #         for j in range(1, n+1):\n",
    "    #             dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i])\n",
    "    #     return dp[N-1][n]\n",
    "\n",
    "# # Linked list, greedy. Regret. [1,2,3,4,5] select 2, replace 2 with 1+3-2=2, delete 1 and 3.\n",
    "# from collections import deque\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "#         q = deque(slices)\n",
    "#         if slices[0] > slice[1]:\n",
    "#             cur_max = max(slices[0], slices[1])\n",
    "#             deque.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        m = len(slices)\n",
    "        tar = m // 3\n",
    "        dp = [[[0] * 2 for _ in range(m)] for _ in range(tar + 1)]  # 当前一共已选i个披萨，最后一个遍历到的披萨为j，最后这个披萨是否选择。\n",
    "        for i in range(tar + 1):\n",
    "            for j in range(1, m):\n",
    "                dp[i][j][0] = max(dp[i][j - 1])\n",
    "                if i > 0:\n",
    "                    dp[i][j][1] = dp[i - 1][j - 1][0] + slices[j - 1]\n",
    "        ans1 = max(dp[-1][-1])\n",
    "\n",
    "        dp = [[[0] * 2 for _ in range(m)] for _ in range(tar + 1)]  # 当前一共已选i个披萨，最后一个遍历到的披萨为j，最后这个披萨是否选择。\n",
    "        for i in range(tar + 1):\n",
    "            for j in range(1, m):\n",
    "                dp[i][j][0] = max(dp[i][j - 1])\n",
    "                if i > 0:\n",
    "                    dp[i][j][1] = dp[i - 1][j - 1][0] + slices[j]\n",
    "        ans2 = max(dp[-1][-1])\n",
    "\n",
    "        return max(ans1, ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        need = n // 3\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, rest, can_last):\n",
    "            if i > n - 1:\n",
    "                return -inf if rest else 0\n",
    "            if rest == 0:\n",
    "                return 0\n",
    "            if i == n - 1 and not can_last:\n",
    "                return -inf if rest else 0\n",
    "            # for i in range(10)\n",
    "            return max(slices[i] + dfs(i + 2, rest - 1, can_last), dfs(i + 1, rest, can_last))\n",
    "        \n",
    "        ans = max(dfs(1, need, True), dfs(0, need, False))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        t = n // 3\n",
    "        \n",
    "        dp1 = [[[-inf, -inf] for _ in range(t+1)] for _ in range(n)]\n",
    "        dp1[0][1][1] = slices[0]\n",
    "        for i in range(1, n):\n",
    "            dp1[i][0][0] = dp1[i-1][0][0]\n",
    "            for k in range(1, t+1):\n",
    "                dp1[i][k][0] = max(dp1[i-1][k][0], dp1[i-1][k][1])\n",
    "                dp1[i][k][1] = dp1[i-1][k-1][0] + slices[i]\n",
    "        \n",
    "        dp2 = [[[-inf, -inf] for _ in range(t+1)] for _ in range(n)]\n",
    "        dp2[0][0][0] = 0\n",
    "        for i in range(1, n):\n",
    "            dp2[i][0][0] = dp2[i-1][0][0]\n",
    "            for k in range(1, t+1):\n",
    "                dp2[i][k][0] = max(dp2[i-1][k][0], dp2[i-1][k][1])\n",
    "                dp2[i][k][1] = dp2[i-1][k-1][0] + slices[i]\n",
    "        \n",
    "        return max(dp1[n-1][-1][0], dp2[n-1][-1][0], dp2[n-1][-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        MAX_INT = 2000 * 600 * 600\n",
    "        N = len(slices) // 3\n",
    "        if N == 1:\n",
    "            return max(slices)\n",
    "        ans = 0\n",
    "        dp = [[[-MAX_INT, -MAX_INT] for _ in range(N + 1)] for _ in range(N * 3)]\n",
    "        dp[0][1][1] = slices[0]\n",
    "        \n",
    "        for i in range(1, N * 3):\n",
    "            for j in range(1, N + 1):\n",
    "                dp[i][j][0] = max(dp[i - 1][j])\n",
    "                dp[i][j][1] = dp[i - 1][j - 1][0] + slices[i]\n",
    "        ans = max([ans, dp[N * 3 - 1][N][0]])\n",
    "\n",
    "        dp = [[[-MAX_INT, -MAX_INT] for _ in range(N + 1)] for _ in range(N * 3)]\n",
    "        dp[0][0][0] = 0\n",
    "        \n",
    "        for i in range(1, N * 3):\n",
    "            dp[i][0][0] = dp[i - 1][0][0] \n",
    "            for j in range(1, N + 1):\n",
    "                dp[i][j][0] = max(dp[i - 1][j])\n",
    "                dp[i][j][1] = dp[i - 1][j - 1][0] + slices[i]\n",
    "        ans = max([ans, dp[N * 3 - 1][N][0], dp[N * 3 - 1][N][1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        f = [[[[0, 0], [0, 0]] for _ in range(n // 3 + 1)] for _ in range(n)]\n",
    "\n",
    "        f[0][1][1][1] = slices[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n // 3 + 1):\n",
    "                for k in range(2):\n",
    "                    f[i][j][k][0] = max(f[i - 1][j][k][0], f[i - 1][j][k][1])\n",
    "                    if i != n - 1 or k == 0:\n",
    "                        f[i][j][k][1] = slices[i] + f[i - 1][j - 1][k][0]\n",
    "        \n",
    "        return max(f[n - 1][n // 3][0][0], f[n - 1][n // 3][0][1], f[n - 1][n // 3][1][0])\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, numbers, n):\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index, remain):\n",
    "            if remain == 0:\n",
    "                return 0\n",
    "            \n",
    "            if index >= len(numbers):\n",
    "                return -1\n",
    "            \n",
    "            results = []\n",
    "            r1 = dfs(index + 2, remain - 1)\n",
    "            if r1 != -1:\n",
    "                results += [r1 + numbers[index]]\n",
    "            \n",
    "            r2 = dfs(index + 1, remain)\n",
    "            if r2 != -1:\n",
    "                results += [r2]\n",
    "            \n",
    "            return max(results) if results else -1\n",
    "        \n",
    "        return dfs(0, n)\n",
    "\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices) // 3\n",
    "        r1 = self.f(slices[1:], n)\n",
    "        r2 = self.f(slices[:-1], n)\n",
    "        return max(r1, r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        global m\n",
    "        m=0\n",
    "        lon=len(slices)\n",
    "      \n",
    "\n",
    "        lo=lon//3\n",
    "        b={}\n",
    "        c={}\n",
    "        for i in range(lon):\n",
    "            b[i]={}\n",
    "            c[i]={}\n",
    "        def fun1(n,q,k,e):\n",
    "            global m\n",
    "            if k==lo-1:\n",
    "                m=max(m,q+slices[n])\n",
    "                return q+slices[n]\n",
    "                # print(m,n,r,e,b)\n",
    "            else:\n",
    "                r=min(lon,lon-(lo-k-2)*2)\n",
    "                if k not in c[n] :\n",
    "                    te=[0]\n",
    "                    for i in range(n+2,r):\n",
    "                        # print(i)\n",
    "                        tem=fun1(i,q+slices[n],k+1,e)\n",
    "                        te.append(tem)\n",
    "                    c[n][k]=[q,max(te)]\n",
    "                    \n",
    "                    # print(c)\n",
    "                    # print(te,n)\n",
    "                    return c[n][k][1]\n",
    "                else:\n",
    "                    if c[n][k][0]<=q:\n",
    "                        c[n][k][1]+=q-c[n][k][0]\n",
    "                        m=max(m,c[n][k][1])\n",
    "                        c[n][k][0]=q\n",
    "                        return c[n][k][1]\n",
    "                    else:\n",
    "                        # c[n][k][1]+=q-c[n][k][0]\n",
    "                        # m=max(m,c[n][k][1])\n",
    "                        # c[n][k][0]=q\n",
    "                        return c[n][k][1]-(c[n][k][0]-q)\n",
    "                    \n",
    "                    \n",
    "        \n",
    "        def fun0(n,q,k,e):\n",
    "            global m\n",
    "            if k==lo-1:\n",
    "                m=max(m,q+slices[n])\n",
    "                return q+slices[n]\n",
    "                # print(m,n,r,e,b)\n",
    "            else:\n",
    "                r=min(lon-1,lon-1-(lo-k-2)*2)\n",
    "            \n",
    "                if k not in b[n] :\n",
    "                    te=[0]\n",
    "                    for i in range(n+2,r):\n",
    "                        # print(i)\n",
    "                        tem=fun0(i,q+slices[n],k+1,e)\n",
    "                        te.append(tem)\n",
    "                    b[n][k]=[q,max(te)]\n",
    "                  \n",
    "                    return b[n][k][1]\n",
    "                else:\n",
    "                    if b[n][k][0]<=q:\n",
    "                        b[n][k][1]+=q-b[n][k][0]\n",
    "                        m=max(m,b[n][k][1])\n",
    "                        b[n][k][0]=q\n",
    "                        return b[n][k][1]\n",
    "                    else:\n",
    "                        # b[n][k][1]+=q-b[n][k][0]\n",
    "                        # m=max(m,b[n][k][1])\n",
    "                        # b[n][k][0]=q\n",
    "                        return b[n][k][1]-(b[n][k][0]-q)\n",
    "                    \n",
    "        fun0(0,0,0,0)\n",
    "        print(m)\n",
    "        for i in range(1,lon-(lo-1)*2):\n",
    "            fun1(i,0,0,i)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class ln:\n",
    "#     def __init__(self,v):\n",
    "#         self.v=v\n",
    "#         self.next=None\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n=len(slices)\n",
    "    # dp=[_ for _ in slices]\n",
    "    # dpick=[set([slices[_],slices[_+1)%n,slices[_-1)%n]]) for _ in range(n)]\n",
    "    # for pick in range(n//3):\n",
    "    #     if pi\n",
    "        pick1res=slices[0]\n",
    "        @functools.lru_cache(maxsize=None)\n",
    "        def pick(idx,end,pickcnt):\n",
    "            if end-idx==pickcnt*2-1:\n",
    "                return sum([slices[_] for _ in range(idx,end,2)])\n",
    "            if end-idx<pickcnt*2-1:\n",
    "                return -1000\n",
    "            if pickcnt==0:\n",
    "                return 0\n",
    "            if idx==0:\n",
    "                # res=0\n",
    "                res=slices[idx]+pick(idx+2,end-1,pickcnt-1);\n",
    "                res2=pick(idx+1,end,pickcnt);\n",
    "                return max(res,res2)\n",
    "            if idx!=0:\n",
    "                return max(slices[idx]+pick(idx+2,end,pickcnt-1),pick(idx+1,end,pickcnt))\n",
    "        return pick(0,n,n//3)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def pick(pizza):\n",
    "        #     if len(pizza)==3:\n",
    "        #         return max(pizza)\n",
    "        #     res=0\n",
    "        #     for p in range(len(pizza)):\n",
    "        #         newpizza=[pizza[_] for _ in range(len(pizza)) if abs((_+1-p)%len(pizza)-1)>1]\n",
    "        #         res=max(res,pizza[p]+pick(newpizza))\n",
    "        #     return res\n",
    "        # return pick(slices)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices):\n",
    "        import copy\n",
    "        n = len(slices)\n",
    "        m = int(n/3)\n",
    "        \n",
    "        Inf = 10**9\n",
    "        base1 = [-Inf,-Inf]\n",
    "        base = [copy.deepcopy(base1) for i in range(m+1)]\n",
    "        g = [copy.deepcopy(base) for i in range(n)]\n",
    "\n",
    "        ans = 0\n",
    "        \n",
    "        f = copy.deepcopy(g)\n",
    "        f[0][0][0] = 0\n",
    "        for i in range(1,n):\n",
    "            for j in range(m+1):\n",
    "                f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1])\n",
    "                f[i][j][1] = f[i-1][j-1][0] + slices[i]\n",
    "                # print(i,j,f[i][j][0],f[i][j][1])\n",
    "\n",
    "        ans = max(f[n-1][m][0],f[n-1][m][1])\n",
    "\n",
    "        f = copy.deepcopy(g)\n",
    "        f[0][1][1] = slices[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(m+1):\n",
    "                f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1])\n",
    "                f[i][j][1] = f[i-1][j-1][0] + slices[i]\n",
    "        ans = max(ans,f[n-1][m][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "\n",
    "        def f(L, m):\n",
    "            n = len(L)\n",
    "            @cache\n",
    "            def dfs(i, rest):                \n",
    "                if rest > (n - i + 1) // 2:\n",
    "                    return -inf \n",
    "                if rest == 0:\n",
    "                    return 0 \n",
    "                if i >= n: \n",
    "                    return -inf \n",
    "                res = -inf \n",
    "                return max(L[i] + dfs(i + 2, rest - 1), dfs(i + 1, rest))\n",
    "            return dfs(0, m)\n",
    "\n",
    "        chosen = len(slices) // 3\n",
    "        return max(f(slices[1:], chosen), f(slices[:-1], chosen))\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(left: int, cnt: int, head_used: int) ->int:\n",
    "            if cnt == 0:\n",
    "                return 0\n",
    "            result = slices[left] + dfs(left + 2, cnt - 1, head_used + int(left == 0))\n",
    "            if cnt + cnt <= len(slices) - left - head_used:\n",
    "                result = max(result, dfs(left + 1, cnt, head_used))\n",
    "            return result\n",
    "        return dfs(0, len(slices)//3, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        # 仔细思考，其实这个题在问的是 在3n数组中选n个不相邻的最大数字和\n",
    "        n = len(slices) // 3\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_n_with_last(i, num, flag=0):\n",
    "            if num == 0:\n",
    "                return 0\n",
    "            if i+2 < 2 * num:\n",
    "                return 0\n",
    "            if flag == 1 and i == 0:\n",
    "                return 0\n",
    "            if num == 1:\n",
    "                return max(slices[1:i+1]) if flag else max(slices[:i+1])\n",
    "            res = max(get_n_with_last(i-1, num, flag), 0)\n",
    "            if i == 3 * n -1:\n",
    "                flag = 1\n",
    "            res = max(res, slices[i] + get_n_with_last(i-2, num-1, flag))\n",
    "            return res\n",
    "\n",
    "        return get_n_with_last(3*n - 1, n, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        N = len(slices)\n",
    "\n",
    "        @cache\n",
    "        def find(i=0, r=N // 3, h=False):\n",
    "            if r == 0: return 0\n",
    "            if math.ceil((N - i - h) / 2) < r: return -inf\n",
    "\n",
    "            return max(\n",
    "                find(i + 1, r, h),\n",
    "                slices[i] + find(i + 2, r - 1, i == 0 or h)\n",
    "            )\n",
    "\n",
    "        return find()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        # 挑n // 3 块不相邻的块，最大化块大小总和\n",
    "        # 环形打家劫舍限制次数版\n",
    "        # 先考虑不是环形的情况\n",
    "        # dp[i][j][0]: 前i块选j块，且选第i块的最大总和\n",
    "        # dp[i][j][1]: 前i块选j块，且不选i块的最大总和\n",
    "        # dp[i][j][0] = dp[i - 1][j - 1][1]\n",
    "        # dp[i][j][1] = max(dp[i - 1][j][0], dp[i - 1][j][1])\n",
    "        n = len(slices)\n",
    "        k = n // 3\n",
    "        dp = [[[0, 0] for _ in range(n // 3)] for _ in range(n)]\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if j == 0:\n",
    "                return 0, 0\n",
    "            if i == 0:\n",
    "                return -inf, -inf\n",
    "\n",
    "            return f(i - 1, j - 1)[1] + slices[i - 1], max(f(i - 1, j))\n",
    "        tmp = slices[1:]\n",
    "        @cache\n",
    "        def g(i, j):\n",
    "            if j == 0:\n",
    "                return 0, 0\n",
    "            if i == 0:\n",
    "                return -inf, -inf\n",
    "\n",
    "            return g(i - 1, j - 1)[1] + tmp[i - 1], max(g(i - 1, j))\n",
    "        return max(max(f(n - 1, n // 3)), max(g(n - 1, n // 3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, arr: List[int]) -> int:\n",
    "        # 以 arr[d] 结尾，选取k个不相领的最大和\n",
    "        n = len(arr)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j, k):\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if i>j:\n",
    "                return -inf\n",
    "\n",
    "            res = -inf\n",
    "            for t in range(j,i-1,-1):\n",
    "                if (t-i+2)//2 <k:\n",
    "                    break\n",
    "                if t==j and (j+1)%n == i:\n",
    "                    res = max(res, arr[t]+dfs(i+1,t-2,k-1))\n",
    "                else:\n",
    "                    res = max(res, arr[t]+dfs(i,t-2,k-1))\n",
    "            return res \n",
    "        return dfs(0,n-1, n//3)\n",
    "\n",
    "\n",
    "\n",
    "0, 1, 2, 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        plies = []\n",
    "        @cache\n",
    "        def dfs(v, l):\n",
    "            if l >= n-1:\n",
    "                return -inf\n",
    "            if v == 1:\n",
    "                return max(plies[l],dfs(v,l+1))\n",
    "            return max(dfs(v,l+1),dfs(v-1,l+2)+plies[l])\n",
    "        plies = slices[0:n-1]\n",
    "        v1 = dfs(n//3,0)\n",
    "        \n",
    "        dfs.cache_clear()\n",
    "        plies = slices[1:n]\n",
    "        v2 = dfs(n//3,0)\n",
    "        return max(v1,v2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        res = 0\n",
    "        for A in [slices[:-1],slices[1:]]:\n",
    "            @cache\n",
    "            def dfs(i,j):\n",
    "                if j==0 or i<0:\n",
    "                    return 0\n",
    "                return max(dfs(i-1,j),A[i]+dfs(i-2,j-1))\n",
    "            res = max(res, dfs(n-2,n//3))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if c == 0:\n",
    "                return 0\n",
    "            if i >= len(slices):\n",
    "                return 0\n",
    "            return max(slices[i] + dfs(i+2, c-1), dfs(i+1, c))\n",
    "        c = len(slices) // 3\n",
    "        a = dfs(1, c)\n",
    "        slices.pop()\n",
    "        dfs.cache_clear()\n",
    "        return max(a, dfs(0, c))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: list[int]) -> int:\n",
    "        inf = 10 **9\n",
    "        def rob(nums: list[int], count) -> int:\n",
    "            n = len(nums)\n",
    "            @cache\n",
    "            def f(i, cnt):\n",
    "                if cnt == 0:\n",
    "                    return 0\n",
    "                if 2 * cnt > (n - i) + (n - i) % 2:\n",
    "                    return -inf\n",
    "                res1 = nums[i] + f(i+2, cnt - 1)\n",
    "                res2 = f(i+1, cnt)\n",
    "                return max(res1, res2)\n",
    "            return f(0, count)\n",
    "\n",
    "        count = len(slices) // 3\n",
    "        res1 = slices[0] + rob(slices[2:-1], count - 1)\n",
    "        res2 = slices[-1] + rob(slices[1: -2], count - 1)\n",
    "        res3 = rob(slices[1:-1], count)\n",
    "        return max(res1, res2, res3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        total_time = n//3\n",
    "\n",
    "        list1 = slices[:-1]\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index_num,c):\n",
    "            if index_num<0:\n",
    "                if c<0:\n",
    "                    return -inf\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                return max(dfs(index_num-1,c),dfs(index_num-2,c-1)+list1[index_num])\n",
    "        n1 = len(list1)\n",
    "        res1 = dfs(n1-1,total_time)\n",
    "        list2 = slices[1:]\n",
    "        n2 = len(list2)\n",
    "\n",
    "        @cache\n",
    "        def dfs(index_num,c):\n",
    "            if index_num<0:\n",
    "                if c<0:\n",
    "                    return -inf\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                return max(dfs(index_num-1,c),dfs(index_num-2,c-1)+list2[index_num])\n",
    "\n",
    "        \n",
    "        res2 = dfs(n2-1,total_time)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # res2 = dfs(n2-1,total_time,list2)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # print(res1)\n",
    "        # slices = slices[1:]\n",
    "        # n = len(slices)\n",
    "        # total_time = n//3\n",
    "        # res2 = dfs(n,total_time)\n",
    "        # print(res1)\n",
    "        # print(res2)\n",
    "        \n",
    "        return max(res1,res2)\n",
    "            \n",
    "\n",
    "\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        def maxArray(nums):#On garantit que nums.length>=5\n",
    "            dp=dict()\n",
    "            dp[0,1]=nums[0]\n",
    "            dp[1,1]=max(nums[0],nums[1])\n",
    "            def dpFunc(N,k):\n",
    "                if (N,k) in dp: return dp[N,k]\n",
    "                if k>N: \n",
    "                    dp[N,k]=0\n",
    "                    return dp[N,k]\n",
    "                if k==0: \n",
    "                    dp[N,k]=0\n",
    "                    return dp[N,k]\n",
    "                dp[N,k]=max(dpFunc(N-1,k), dpFunc(N-2,k-1)+nums[N])\n",
    "                return dp[N,k]\n",
    "            return dpFunc(len(nums)-1, n//3)\n",
    "        n=len(slices)\n",
    "        if n==3: return max(slices)\n",
    "        else: return max(maxArray(slices[:n-1]), maxArray(slices[1:]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(i,num,slices):\n",
    "            if num>i+1 or i<0:return float('-inf')\n",
    "            if num==1:return slices[i] if i==0 else max(slices[i],dp(i-1,num,slices))\n",
    "            res= max(slices[i]+dp(i-2,num-1,slices),dp(i-1,num,slices))\n",
    "            #print(i,num,slices,res)\n",
    "            return res\n",
    "\n",
    "        \n",
    "        n=len(slices)\n",
    "\n",
    "        return max(dp(n-2,n//3,tuple(slices[1:])),dp(n-2,n//3,tuple(slices[:n-1])))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j, slices):\n",
    "            if j == 0:\n",
    "                return 0\n",
    "            if i == 0 and j == 1:\n",
    "                return slices[0]\n",
    "            if i == 1 and j == 1:\n",
    "                return max(slices[0], slices[1])\n",
    "            if i < j:\n",
    "                return -1\n",
    "            a1 = dfs(i-2,j-1,slices)+slices[i]\n",
    "            a2 = dfs(i-1,j,slices)\n",
    "            ans = max(a1, a2)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        slices1 = slices[1:]\n",
    "        slices2 = slices[0:-1]\n",
    "        k = len(slices)\n",
    "\n",
    "        return max(dfs(k-2, k//3, tuple(slices1)), dfs(k-2, k//3, tuple(slices2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, cur: int, upper: int) -> int:\n",
    "            if cur == 0:\n",
    "                return 0\n",
    "            if upper - i < cur:\n",
    "                return -inf\n",
    "            return max(dfs(i + 1, cur, upper), dfs(i + 2, cur - 1, upper) + slices[i])\n",
    "\n",
    "        n = len(slices)\n",
    "        mx = n // 3\n",
    "        return max(dfs(0, mx, n - 1), dfs(1, mx, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        hint = list()\n",
    "        memo = dict()\n",
    "        def backtrace(left, right, n):\n",
    "            if (left, right, n) in memo:\n",
    "                return memo[(left, right, n)]\n",
    "            if n == 0:\n",
    "                ret = 0\n",
    "            else:\n",
    "                #ret = slices[left] + backtrace(left + 2, right - 1, n - 1)\n",
    "                ret = 0\n",
    "                for idx in range(left, right - 2 * n + 3):\n",
    "                    ret = max(ret, slices[idx] + backtrace(idx + 2, right, n - 1))\n",
    "            hint.append((left, right, n, ret))\n",
    "            memo[(left, right, n)] = ret\n",
    "            return ret\n",
    "        n = len(slices) // 3\n",
    "        return max(backtrace(1, len(slices) - 1, n), slices[0] + backtrace(2, len(slices) - 2, n - 1))#, hint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        # 去头去尾双dp(i,k)->[0,i+1]选k块披萨+两递归出口\n",
    "        n = len(slices) // 3\n",
    "\n",
    "        def single_dp(slices):\n",
    "            @functools.cache\n",
    "            def dp(i, k):\n",
    "                if k == 0:\n",
    "                    # 递归出口1: 不能选择, 有效, 返回0\n",
    "                    return 0\n",
    "                if i < 0:\n",
    "                    # 递归出口2: 没有可选披萨但需要选择, 无效, 返回-inf\n",
    "                    return -float(\"inf\")\n",
    "                # 两种转移情况, 选i或不选i\n",
    "                return max(dp(i - 1, k), dp(i - 2, k - 1) + slices[i])\n",
    "\n",
    "            return dp(len(slices) - 1, n)\n",
    "\n",
    "        return max(single_dp(slices[:-1]), single_dp(slices[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "\n",
    "        def maxSizeSlices_Base(slices: List[int]):\n",
    "            @cache\n",
    "            def dp(end: int, count: int, curSelected: bool):\n",
    "                if count == 0 or end < count * 2 - 2:\n",
    "                    return 0\n",
    "                if curSelected:\n",
    "                    return max(\n",
    "                        dp(end - 1, count - 1, False) + slices[end],\n",
    "                        dp(end - 1, count, True)\n",
    "                    )\n",
    "                else:\n",
    "                    return dp(end - 1, count, True)\n",
    "            return dp(len(slices) - 1, len(slices) // 3 + 1, True)\n",
    "        \n",
    "        return max(\n",
    "            maxSizeSlices_Base(slices[:-1]),\n",
    "            maxSizeSlices_Base(slices[1:]),\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    # 序列中取k个不连续的数值的最大和\n",
    "    @lru_cache(typed=False, maxsize=12800000)\n",
    "    def dp(self, start, end, k):\n",
    "        s = self.s\n",
    "\n",
    "        n = end - start + 1\n",
    "        max_k = n // 2 + 1 if n % 2 == 1 else n // 2\n",
    "        if k > max_k:\n",
    "            return -0x7fffffff\n",
    "\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = self.dp(start, end-1, k)\n",
    "        if end == self.max_pos:\n",
    "            ans = max(ans, s[end] + self.dp(start + 1, end - 2, k - 1))\n",
    "        else:\n",
    "            ans = max(ans, s[end] + self.dp(start, end - 2, k - 1))\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        self.max_pos = len(slices) - 1\n",
    "        self.s = slices\n",
    "\n",
    "        return self.dp(0, len(slices)-1, len(slices) // 3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    # 序列中取k个不连续的数值的最大和\n",
    "    @lru_cache(typed=False, maxsize=12800000)\n",
    "    def dp(self, start, end, k):\n",
    "        s = self.s\n",
    "\n",
    "        n = end - start + 1\n",
    "        max_k = n // 2 + 1 if n % 2 == 1 else n // 2\n",
    "        if k > max_k:\n",
    "            return -0x7fffffff\n",
    "\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = -1\n",
    "        for last_pos in range(start + 2*(k-1), end+1):\n",
    "            if last_pos == self.max_pos:\n",
    "                ans = max(ans, s[last_pos] + self.dp(start+1, last_pos-2, k-1))\n",
    "            else:\n",
    "                ans = max(ans, s[last_pos] + self.dp(start, last_pos-2, k-1))\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        self.max_pos = len(slices) - 1\n",
    "        self.s = slices\n",
    "\n",
    "        return self.dp(0, len(slices)-1, len(slices) // 3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # dynamic programming\n",
    "# class Solution:\n",
    "#     def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "#         x = len(slices)\n",
    "#         y = x // 3\n",
    "#         g1 = slices[1:]\n",
    "#         g2 = slices[:-1]\n",
    "\n",
    "#         f1 = [[0] * (y + 1) for _ in range(x + 1)]\n",
    "#         f2 = [[0] * (y + 1) for _ in range(x + 1)]\n",
    "\n",
    "#         for j in range(1, y + 1):\n",
    "#             for i in range(2, x + 1):\n",
    "#                 f1[i][j] = max(f1[i - 1][j], f1[i - 2][j - 1] + g1[i - 2])\n",
    "#                 f2[i][j] = max(f2[i - 1][j], f2[i - 2][j - 1] + g2[i - 2])\n",
    "#         return max(f1[-1][-1], f2[-1][-1])\n",
    "\n",
    "# # dfs\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        x = len(slices)\n",
    "        y = x // 3\n",
    "        @cache\n",
    "        def dfs(i:int, j:int, mini:int)->int:\n",
    "            if j == 0:   return 0\n",
    "            if i < mini: return -inf\n",
    "            return max(dfs(i - 1, j, mini), dfs(i - 2, j - 1, mini) + slices[i])\n",
    "        return max(dfs(x - 1, y, 1), dfs(x - 2, y, 0))\n",
    "\n",
    "        # f1, f2 = slices[1:], slices[:-1]\n",
    "        # @cache\n",
    "        # def dfs1(i:int, j:int)->int:\n",
    "        #     if j == 0:\n",
    "        #         return 0\n",
    "        #     if i < 0:\n",
    "        #         return -inf\n",
    "\n",
    "        #     return max(dfs1(i - 1, j), dfs1(i - 2, j - 1) + f1[i])\n",
    "        \n",
    "        # @cache\n",
    "        # def dfs2(i:int, j:int)->int:\n",
    "        #     if j == 0:\n",
    "        #         return 0\n",
    "        #     if i < 0:\n",
    "        #         return -inf\n",
    "\n",
    "        #     return max(dfs2(i - 1, j), dfs2(i - 2, j - 1) + f2[i])\n",
    "        \n",
    "        # return max(dfs1(x-2, y), dfs2(x - 2, y))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices) // 3\n",
    "        def f(s: List[int]) -> int:\n",
    "            m = len(s)\n",
    "            @cache\n",
    "            def dfs(i: int, j: int) -> int:\n",
    "                if j == 0:\n",
    "                    return 0\n",
    "                if i == 0:\n",
    "                    return s[0] if j == 1 else 0\n",
    "                if i == 1:\n",
    "                    return max(s[0], s[1]) if j == 1 else 0\n",
    "                a = s[i] + dfs(i - 2, j - 1)\n",
    "                b = dfs(i - 1, j)\n",
    "                return max(a, b)\n",
    "            return dfs(m - 1, n)\n",
    "        return max(f(slices[:-1]), f(slices[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n_3 = len(slices)\n",
    "        n = n_3 / 3\n",
    "        slices1 = slices[:-1]\n",
    "        slices2 = slices[1:]\n",
    "        @cache\n",
    "        def dp1(i, j) -> int:\n",
    "            if i <= 0 or j <= 0: return 0\n",
    "            if j == 1: return max(slices1[:i])\n",
    "\n",
    "            return max(slices1[i - 1] + dp1(i - 2, j - 1), dp1(i - 1, j))\n",
    "\n",
    "        @cache\n",
    "        def dp2(i, j) -> int:\n",
    "            if i <= 0 or j <= 0: return 0\n",
    "            if j == 1: return max(slices2[:i])\n",
    "\n",
    "            return max(slices2[i - 1] + dp2(i - 2, j - 1), dp2(i - 1, j))\n",
    "        return max(dp1(n_3 - 1, n), dp2(n_3 - 1, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, nums: List[int]) -> int:\n",
    "        it =len(nums)//3\n",
    "        a=nums[:-1]\n",
    "        b=nums[1:]\n",
    "        @lru_cache(None)\n",
    "        def dp1(x,deep):\n",
    "            if x<0 or deep==0:\n",
    "                return 0\n",
    "            return max(dp1(x-1,deep),dp1(x-2,deep-1)+a[x])\n",
    "        @lru_cache(None)\n",
    "        def dp2(x,deep):\n",
    "            if x<0 or deep==0:\n",
    "                return 0\n",
    "            return max(dp2(x-1,deep),dp2(x-2,deep-1)+b[x])\n",
    "        return max(dp1(len(nums)-2,it),dp2(len(nums)-2,it))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        m = len(slices)\n",
    "        n = m // 3\n",
    "        # 在3n个位置，选n个位置的披萨，并且要求不相邻\n",
    "        # 首尾两个位置不能同时出现披萨\n",
    "        # 因此0到n-2， 1到n，分别求一下\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, t):\n",
    "            if j == 0:\n",
    "                return 0\n",
    "            if i >= t:\n",
    "                return -inf\n",
    "            # 当前不选披萨\n",
    "            res = dfs(i+1, j, t)\n",
    "            # 当前选披萨\n",
    "            res = max(res, dfs(i+2, j-1, t) + slices[i])\n",
    "            return res \n",
    "        \n",
    "\n",
    "        return max(dfs(0, n, m-1), dfs(1, n, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        tn = len(slices)\n",
    "        n = tn//3\n",
    "        tn -= 1\n",
    "        def f(slices):\n",
    "            @cache\n",
    "            def dfs(pos,k):\n",
    "                if pos >= tn or k == n:return 0\n",
    "                res = max(dfs(pos+1,k),dfs(pos+2,k+1)+slices[pos])\n",
    "                return res\n",
    "            return dfs(0,0)\n",
    "        return max(f(slices[1:]),f(slices[:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        # def calculate(slices):\n",
    "        #     N, n = len(slices), (len(slices) + 1) // 3\n",
    "        #     dp = [[-10**9 for i in range(n + 1)] for j in range(N)]\n",
    "        #     dp[0][0], dp[0][1] = 0, slices[0]\n",
    "        #     dp[1][0], dp[1][1] = 0, max(slices[0], slices[1])\n",
    "        #     for i in range(2, N, 1):\n",
    "        #         dp[i][0] = 0\n",
    "        #         for j in range(1, n + 1, 1):\n",
    "        #             dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i])\n",
    "        #     return dp[N - 1][n]\n",
    "        # v1 = slices[1:]\n",
    "        # v2 = slices[0:-1]\n",
    "        # ans1 = calculate(v1)\n",
    "        # ans2 = calculate(v2)\n",
    "        # return max(ans1, ans2)\n",
    "        @cache\n",
    "        def dfs(i, boundary, cnt):\n",
    "            if i < boundary or cnt >= (n//3):\n",
    "                return 0\n",
    "            # if memo[cnt][i] != -1:\n",
    "            #     return memo[cnt][i]\n",
    "            # memo[cnt][i] = max(dfs(i-1, boundary, cnt), dfs(i - 2, boundary, cnt+1) + nums[i])\n",
    "            # return memo[cnt][i]\n",
    "            return max(dfs(i-1, boundary, cnt), dfs(i - 2, boundary, cnt+1) + slices[i])\n",
    "        # nums = slices\n",
    "        n = len(slices)\n",
    "        memo = [[-1 for i in range(n)] for j in range(n//3)]\n",
    "        cnt = 0\n",
    "        r1 = dfs(n - 1, 1, cnt)\n",
    "        memo = [-1]*n\n",
    "        cnt = 0\n",
    "        r2 = dfs(n - 2, 0, cnt)\n",
    "        return max(r1, r2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        slices1=slices[1:]\n",
    "        slices2=slices[:-1]\n",
    "        n=len(slices)\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j<0 or i<0:\n",
    "                return -float('inf')\n",
    "            if j==0:\n",
    "                return 0\n",
    "            if j==1 and i==0:\n",
    "                return slices1[0] \n",
    "            if j==1 and i==1:\n",
    "                return max(slices1[0], slices1[1])\n",
    "            print(i)\n",
    "            v=max(dfs(i-2,j-1)+slices1[i],dfs(i-1,j))\n",
    "            return v\n",
    "        @cache    \n",
    "        def dfs2(i,j):\n",
    "            if j<0 or i<0:\n",
    "                return -float('inf')\n",
    "            if j==0:\n",
    "                return 0\n",
    "            if j==1 and i==0:\n",
    "                return slices2[0] \n",
    "            if j==1 and i==1:\n",
    "                return max(slices2[0], slices2[1]) \n",
    "            v=max(dfs2(i-2,j-1)+slices2[i],dfs2(i-1,j))\n",
    "            return v\n",
    "        a=dfs(n-2,n//3)\n",
    "        print('   ')\n",
    "        b=dfs2(n-2,n//3)\n",
    "        print(a,b)\n",
    "        return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        t = n // 3\n",
    "        @cache\n",
    "        def dfs(i,j,t):\n",
    "            if t == 0:\n",
    "                return 0\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            # 选第一个\n",
    "            if i == 0:\n",
    "                ans = slices[i] + dfs(i + 2,j - 1,t - 1)\n",
    "            else:\n",
    "                ans = slices[i] + dfs(i + 2,j,t - 1)\n",
    "            # 不选第一个\n",
    "            ans = max(ans,dfs(i + 1,j,t))\n",
    "            return ans\n",
    "        return dfs(0,n,t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n=len(slices)\n",
    "        @cache\n",
    "        def dfs(i,k,lit):\n",
    "            if i>=lit:return 0\n",
    "            if k==0:return 0\n",
    "            return max(slices[i]+dfs(i+2,k-1,lit),dfs(i+1,k,lit))\n",
    "        return max(dfs(0,n//3,n-1),dfs(1,n//3,n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        t = len(slices) // 3\n",
    "\n",
    "        def helper(slices):\n",
    "            n = len(slices)\n",
    "            @cache\n",
    "            def f(i, cnt):\n",
    "                if i >= n:\n",
    "                    return 0 if cnt == t else -inf\n",
    "                # 1、不选i\n",
    "                p1 = f(i + 1, cnt)\n",
    "                # 2、选i\n",
    "                p2 = slices[i] + f(i + 2, cnt + 1)\n",
    "                return max(p1, p2)\n",
    "            \n",
    "            return f(0, 0)\n",
    "        \n",
    "        return max(helper(slices[1:]), helper(slices[:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices) // 3\n",
    "        \n",
    "        def cal(sublist: List[int]) -> int:\n",
    "            l = len(sublist)\n",
    "\n",
    "            @cache\n",
    "            def dfs(i: int, cnt: int) -> int:\n",
    "                if i >= l:\n",
    "                    return 0 if cnt==0 else -float('inf')\n",
    "                \n",
    "                return max(dfs(i+1, cnt), dfs(i+2, cnt-1)+sublist[i])\n",
    "\n",
    "            return dfs(0, n)\n",
    "        \n",
    "        sub1, sub2 = slices[:-1], slices[1:]\n",
    "        # print(sub1, ' ', sub2)\n",
    "\n",
    "        return max(cal(sub1), cal(sub2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if i == n-1 and k or i >= n:\n",
    "                return 0 if j == n//3 else -inf\n",
    "            res = f(i+1,j,k)\n",
    "            return max(res, slices[i] + f(i+2,j+1,k or i == 0))\n",
    "        \n",
    "        return f(0,0,False)\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = n//3\n",
    "        # 偷第一个，那么最后一个不能偷，第二个不能偷\n",
    "        @cache\n",
    "        def dfs1(i,c):\n",
    "            if i >= n-1:\n",
    "                if c == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -inf\n",
    "            res1 = dfs1(i+1,c)\n",
    "            res2 = dfs1(i+2,c-1) + nums[i]\n",
    "            return max(res1,res2)\n",
    "        # 不偷第一个\n",
    "        @cache\n",
    "        def dfs2(i,c):\n",
    "            if i >= n:\n",
    "                return 0 if c == 0 else -inf\n",
    "            res1 = dfs2(i+1,c)\n",
    "            res2 = dfs2(i+2,c-1) + nums[i]\n",
    "            return max(res1,res2)\n",
    "        return max(dfs1(2,m-1) + nums[0] ,dfs2(1,m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = n//3\n",
    "        # 选第一个那么最后一个不能选\n",
    "        from functools import cache\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i >= n-1:\n",
    "                return 0 if c == 0 else -inf\n",
    "            return max(dfs(i+1,c),dfs(i+2,c-1) + nums[i])\n",
    "\n",
    "        @cache\n",
    "        def dfs1(i,c):\n",
    "            if i >= n:\n",
    "                return 0 if c == 0 else -inf\n",
    "            return max(dfs1(i+1,c),dfs1(i+2,c-1) + nums[i])\n",
    "        return max(dfs(0,m),dfs1(1,m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:\n",
    "        n = len(slices)\n",
    "        total_time = n // 3\n",
    "        list1 = slices[1:]\n",
    "        n1 = len(list1)\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i<0:\n",
    "                if c<0:\n",
    "                    return -inf\n",
    "                return 0\n",
    "            return max(dfs(i-1,c),dfs(i-2,c-1)+list1[i])\n",
    "        res1 = dfs(n1-1,total_time)\n",
    "        list2 = slices[:-1]\n",
    "        n2 = len(list2)\n",
    "        @cache\n",
    "        def dfs2(i,c):\n",
    "            if i<0:\n",
    "                if c<0:\n",
    "                    return -inf\n",
    "                return 0\n",
    "            return max(dfs2(i-1,c),dfs2(i-2,c-1)+list2[i])\n",
    "        res2 = dfs2(n2-1,total_time)\n",
    "        return max(res1,res2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  # 环形打架劫舍变形题\n",
    "    def maxSizeSlices(self, slices: List[int]) -> int:  \n",
    "        m = len(slices)\n",
    "        n = m // 3\n",
    "        def cal(a: List[int]) -> int:\n",
    "            @cache\n",
    "            def dfs(i: int, s: int) -> int:\n",
    "                if i >= len(a): return 0 if s == 0 else -inf\n",
    "                # 选\n",
    "                res = dfs(i+2, s-1) + a[i]\n",
    "                # 不选\n",
    "                res = max(res, dfs(i+1, s))\n",
    "                return res\n",
    "            return dfs(0, n)\n",
    "        a, b = slices[: -1], slices[1: ]\n",
    "        return max(cal(a), cal(b))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
